This invention relates to Bose-Chaudhuri-Hocquenghem (BCH) decoders, and in particular to programmable error and erasure correction decoders having a systolic architecture.
Although BCH codes are powerful and efficient, their decoding algorithms are computationally intensive finite-field procedures which require special-purpose hardware for high-speed area-efficient implementations. The solution of the key equation is the most difficult of the decoding operations and has been the subject of considerable research activity. Recent focus has been on developing algorithms that are well suited for VLSI implementation. Liu has proposed solving the key equation by a direct implementation of the Berlekamp-Massey algorithm ("Architecture for VLSI design of Reed-Solomon decoders" by K. Y. Liu, in IEEE Trans. Computers, Vol. C-33, No. 2, February 1984). This approach requires a field-element inversion within every iteration and a global broadcast of the discrepancy. These are both negative features, and the global broadcast is potentially a limiting factor in the performance of the system. A group at the Jet Propulsion Laboratory has developed a decoder where the key equation is solved using a greatest common divisor (GCD) implementation developed by Brent and Kung ("A VLSI design of a pipeline Reed-Solomon Decoder" by H. M. Shao et al. in IEEE Trans. Computers, Vol. C-34, No. 5, May 1985, and "Systolic VLSI arrays for linear-time GCD computations" by R. P. Brent and H. T. Kung in VLSI '83, North-Holland, 1983). This systolic GCD algorithm requires 2t cells and requires only local (cell-to-cell) communication. In addition, there is no need for a field-element inversion. However, every cell must compute several logical control signals and the resulting systolic cell is not regular.